package day_7_8;

public class Main2 {
    /**
     * 148. 排序链表
     * https://leetcode.cn/problems/sort-list/description/?envType=study-plan-v2&envId=top-100-liked
     */
    public class ListNode {
        int val;
        ListNode next;
        ListNode() {}
        ListNode(int val) { this.val = val; }
        ListNode(int val, ListNode next) { this.val = val; this.next = next; }
    }
    public ListNode sortList(ListNode head) {
        // 归并排序
        // 使用双指针进行查找中间节点
        if(head == null || head.next == null) {
            return head;
        }
        ListNode fast = head.next; //这里可以使其进行均匀分割，防止栈溢出
        ListNode slow = head;
        while(fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        ListNode tmp = slow.next;
        slow.next = null;
        ListNode left = sortList(head);
        ListNode right = sortList(tmp);
        // 进行重新构造
        ListNode ret = new ListNode(0);
        ListNode cur = ret;
        while(left != null && right != null) {
            if(left.val < right.val) {
                cur.next = left;
                left = left.next;
            }else {
                cur.next = right;
                right = right.next;
            }
            cur = cur.next;
        }

        cur.next = (left != null ? left : right);

        return ret.next;
    }
}
